package _binary_tree

import common.v1.Node
import org.junit.Assert
import org.junit.Test
import java.util.*
import kotlin.collections.ArrayList

/*
 https://programmercarl.com/%E5%91%A8%E6%80%BB%E7%BB%93/20200927%E4%BA%8C%E5%8F%89%E6%A0%91%E5%91%A8%E6%9C%AB%E6%80%BB%E7%BB%93.html#%E5%91%A8%E4%BA%8C
 https://leetcode.cn/problems/n-ary-tree-postorder-traversal/description/

 590. N 叉树的后序遍历

示例 1：
输入：root = [1,null,3,2,4,null,5,6]
输出：[5,6,3,2,4,1]

示例 2：
输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[2,6,14,11,7,3,12,8,4,13,9,10,5,1]
 */
class leetcode_590 {
    @Test
    fun test_1() {
        val root = Node(1)
        val n2 = Node(2)
        val n3 = Node(3)
        val n4 = Node(4)
        val n5 = Node(5)
        val n6 = Node(6)
        root.children = arrayListOf(n3, n2, n4)
        n3.children = arrayListOf(n5, n6)
        val actual = postorder(root)
        val expect = arrayListOf(5,6,3,2,4,1)
        Assert.assertEquals(expect.toString(), actual.toString())
    }


    @Test
    fun test_2() {
        val root = Node(1)
        val n2 = Node(2)
        val n3 = Node(3)
        val n4 = Node(4)
        val n5 = Node(5)
        val n6 = Node(6)
        val n7 = Node(7)
        val n8 = Node(8)
        val n9 = Node(9)
        val n10 = Node(10)
        val n11 = Node(11)
        val n12 = Node(12)
        val n13 = Node(13)
        val n14 = Node(14)
        root.children = arrayListOf(n2, n3, n4, n5)
        n3.children = arrayListOf(n6, n7)
        n4.children = arrayListOf(n8)
        n5.children = arrayListOf(n9, n10)
        n7.children = arrayListOf(n11)
        n8.children = arrayListOf(n12)
        n9.children = arrayListOf(n13)
        n11.children = arrayListOf(n14)

        val actual = postorder(root)
        val expect: ArrayList<Int> = arrayListOf(2,6,14,11,7,3,12,8,4,13,9,10,5,1)
        Assert.assertEquals(expect.toString(), actual.toString())
    }


    private fun postorder(root: Node?): List<Int> {
        val result: ArrayList<Int> = ArrayList<Int>()
        // traverse(root,result)
        // traverse2(root,result)
        traverse3(root, result)
        return result
    }

    // 深度遍历 - 后序遍历 - 递归
    private fun traverse(root: Node?, result: ArrayList<Int>) {
        // S - N
        // T - N
        if (null == root) {
            return
        }
        for (child in root.children) {
            traverse(child, result)
        }
        result.add(root.`val`)
    }

    // 深度遍历 - 后序遍历 - 迭代
    private fun traverse2(root: Node?, result: ArrayList<Int>) {
        // S - N
        // T - N
        if (null == root) {
            return
        }

        val stack: LinkedList<Node> = LinkedList<Node>()
        stack.push(root)

        while (!stack.isEmpty()) {
            val node: Node = stack.pop()
            result.add(node.`val`)
            val size = node.children.size
            if (size >= 1) {
                for (i in 0..size - 1) {
                    stack.push(node.children.get(i))
                }
            }
        }
        result.reverse()
    }

    // 深度遍历 - 后序遍历 - 迭代（统一写法）
    private fun traverse3(root: Node?, result: ArrayList<Int>) {
        // S - N
        // T - N
        if (null == root) {
            return
        }
        val stack: LinkedList<Pair<Node, Boolean>> = LinkedList<Pair<Node, Boolean>>()
        stack.push(Pair<Node, Boolean>(root, false))


        while (!stack.isEmpty()) {
            val pair: Pair<Node, Boolean> = stack.pop()
            val node: Node = pair.first
            val visited: Boolean = pair.second
            if (visited) {
                result.add(node.`val`)
                continue
            }
            stack.push(Pair<Node, Boolean>(node, true))
            val size = node.children.size
            if (size >= 1) {
                for (i in size - 1 downTo 0)
                    node.children.get(i)?.let {
                        stack.push(Pair<Node, Boolean>(it, false))
                    }
            }
        }
    }
}